"""
Problem 16: https://projecteuler.net/problem=16

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.8.3
@creat_time = 2022/5/8
'''

        
def solution1(c: int = 1000) -> int:
    '''
    >>> solution1(0)
    1
    >>> solution1(1)
    2
    >>> solution1(13)  # 2^13 = 8192
    20
    >>> solution1(15)  # 2^15 = 32768
    26
    '''
    
    total = 0
    nc = 2**c
    
    while nc != 0:
        tmp = divmod(nc, 10)
        total += tmp[1]
        nc = tmp[0]
        
    return total

def solution2(c: int = 1000) -> int:
    '''
    >>> solution2(0)
    1
    >>> solution2(1)
    2
    >>> solution2(13)  # 2^13 = 8192
    20
    >>> solution2(15)  # 2^15 = 32768
    26
    '''
    
    return sum(map(int, str(2**c)))
    

def power(n: int = 2, c: int = 1000) -> str:
    
    '''
    comput n^c when n is in [2,3,...,9] and c is very large, e.g. n=2, c=1000
    
    >>> power(5,1)
    '5'
    >>> power(9,3)
    '729'
    >>> import math
    >>> assert str(int(math.pow(2,1000))) == power(2,1000) 
    
    math.pow(2, 2000)  # raise OverflowError: math range error
    
    >>> power(2,2000)[-4:]
    '9376'
    '''
    
    if n > 9:
        raise ValueError('n is a number of [1,2,3,...,9]')
    
    if c == 0:
        return 1
    
    import math
    c10 = int(c * math.log10(n)) + 1  # 2^1000 has c10 = 302
    
    # at first,  pow_nc = [n,0,0,0,...,0]  # len = 302
    POW_nc = [0] * c10
    POW_nc[0] = n  # one time
    
    for _ in range(c-1):  # c-1 times of *n 
        carry = 0
        for i in range(c10):
            tmp = POW_nc[i] * n + carry
            if tmp >= 10:
                carry = tmp // 10
                POW_nc[i] = tmp - carry * 10
            else:
                carry = 0
                POW_nc[i] = tmp
    
    return ''.join(map(str, POW_nc[::-1]))
    

def solution3(c: int = 1000) -> int:
    # like solution2()
    
    return sum(map(int, power(2,c)))


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    print(f'solution1() = {solution1()}')
    # 1366
    print(f'solution2() = {solution2()}')
    print(f'solution3() = {solution3()}')

    
'''
    In solution1() and solution2(), compute 2^1000 directly is too mazing!
    
    **********************************************************************
    9-ary representation:
    
    2^(9^k) = 2 mod 10 can be proved by induction.
    
    for 1000, apply 9-ary representation
        1000 = 9^3 + 3* 9^2 + 3* 9^1 + 1* 9^0
             = (1331)9
             
    >>> assert int('1331',9) == 1000
    
    2^1000 = 2^(9^3 + 3* 9^2 + 3* 9^1 + 1* 9^0)
           = 2^(9^3) * (2^(9^2))^3 * (2^(9^1))^3 * (2^(9^0))
           = 2 * 2^3 * 2^3 * 2
           = 2^(1 + 3 + 3 + 1)
           = 2^8
           = 6 mod 10
           
    therefore, 2^1000 last digit is 6.
    
    More generally,
    
        2^c = 2 ^ sum(d0,d1,d2,d3,...) mod 10, in which (d0,d1,d2,d3,...) 
        represents the coefficient of c 9-ary representation
    
    **********************************************************************    
    8-ary representation:
        
        2^(8^0) = 2 mod 10, 2^(8^1) = 6 mod 10, 2^(8^2) = 6 mod 10, ...
        
           2^c = (2 ^ d0) * 6 ^ sum(d1,d2,d3,...) mod 10
               = (2 ^ d0) * 6                     mod 10   if c >= 8
               = (2 ^ d0)                         mod 10   if c <  8
        
        So, the last digit of 8-ary representation of c determine the
        last digit of 2^c
        
        >>> assert oct(1000) == '0o1750'
        >>> assert oct(1001) == '0o1751'
        
    **********************************************************************
    In Python, we can quickliy get the result:
        
        import math
        math.pow(2, 1000, 10)  # python 3.8.3, pow expected 2 arguments, pow(x, y, /)

    '''


    


